package com.yanceysong.codetop.s61_s70;

public class S63_Mid_34_在排序数组中查找元素的第一个和最后一个位置 {
    /**
     * .S63_Mid_34_在排序数组中查找元素的第一个和最后一个位置
     * .<p>
     * .题目链接：<a href="https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/">https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/</a>
     * .<p>
     * .题目描述：
     * .给你一个按照非递减（升序，允许重复）顺序排列的整数数组 nums，和一个目标值 target。
     * .请你找出给定目标值在数组中的【开始位置】和【结束位置】（即第一次出现和最后一次出现的索引）。
     * .如果数组中不存在目标值 target，返回 [-1, -1]。
     * .要求算法时间复杂度必须为 O(log n)。
     * .<p>
     * .示例1：
     * .输入：nums = [5,7,7,8,8,10], target = 8
     * .输出：[3,4]
     * .解释：8第一次出现位置索引3，最后出现位置索引4。
     * .<p>
     * .示例2：
     * .输入：nums = [5,7,7,8,8,10], target = 6
     * .输出：[-1,-1]
     * .解释：数组中不存在值6。
     * .<p>
     * .示例3：
     * .输入：nums = [], target = 0
     * .输出：[-1,-1]
     * .<p>
     * .示例4：
     * .输入：nums = [1], target = 1
     * .输出：[0,0]
     * .<p>
     * .示例5：
     * .输入：nums = [2,2,2,2,2], target = 2
     * .输出：[0,4]
     * .<p>
     * .核心标签：二分查找 / 数组 / 边界定位 / 搜索算法
     * .<p>
     * .解题思路总览：
     * .想要 O(log n) 且返回首尾位置 => 应使用二分查找定位“左右边界”。
     * .经典做法：写一个带参数的二分函数 findBoundary(nums, target, findLeft)；
     * . - 当 findLeft = true 时：找“第一个 >= target 的位置” (lower bound)。
     * . - 当 findLeft = false 时：找“第一个 > target 的位置” (upper bound)。最后答案右边界 = upper bound - 1。
     * .这样可以统一逻辑，避免分别写两个相似的二分。
     * .<p>
     * .关键点（二分边界的判定思想）：
     * .lower bound：最左满足 nums[i] >= target 的位置。
     * .upper bound：最左满足 nums[i] > target 的位置。
     * .若 target 存在：左边界 = lowerBound；右边界 = upperBound - 1。
     * .若不存在：检查得到的候选范围是否有效（下标越界或值不等）。
     * .<p>
     * .ASCII 图解（示例 nums=[5,7,7,8,8,10], target=8）：
     * .索引:    0 1 2 3 4 5
     * .数值:    5 7 7 8 8 10
     * .lowerBound(>=8)  -> 3 (第一个>=8)
     * .upperBound(>8)   -> 5 (第一个>8，即10所在位置)
     * .右边界 = upperBound - 1 = 4
     * .最终区间 = [3,4]
     * .<p>
     * .为什么用“第一个 >=” 和 “第一个 >” 比较好？
     * .- 保持对重复元素的统一处理；逻辑简单。
     * .- upperBound - 1 自动得到“最后一个 == target”的位置。
     * .<p>
     * .易错点 & 边界：
     * .- 空数组直接返回 [-1,-1]。
     * .- 若 leftIdx > rightIdx 或下标不合法，需要返回 [-1,-1]。
     * .- 检查返回的两个边界是否真的对应 target。
     * .- mid 计算最好用 mid = left + (right - left)/2 防止溢出（这里数组长度一般安全）。
     * .- findBoundary 中维护一个答案 ans 初始为 nums.length，代表未找到时返回“超尾”位置。
     * .<p>
     * .复杂度分析：
     * .- 时间复杂度：O(log n)，两次二分查找。
     * .- 空间复杂度：O(1)。
     * .<p>
     * .扩展：也可以先做一次标准二分查找找到任一 target 位置，再向左右线性扩展，但那样在全重复情况下退化为 O(n)。因此不符合题目要求。
     */
    public int[] searchRange(int[] nums, int target) {
        // 调用“寻找边界”函数：

        // 第一个 >= target 的位置
        int leftBoundaryIndex = findBoundary(nums, target, true);
        // 第一个 > target 的位置（右边界是前一个）
        int rightBoundaryExclusive = findBoundary(nums, target, false);
        // 实际最后一个 == target 的位置
        int rightBoundaryIndex = rightBoundaryExclusive - 1;

        // 验证：左边界应 <= 右边界；右边界在数组范围内；且值确实等于 target
        if (leftBoundaryIndex <= rightBoundaryIndex
            && rightBoundaryIndex < nums.length
            && leftBoundaryIndex >= 0
            && nums[leftBoundaryIndex] == target
            && nums[rightBoundaryIndex] == target) {
            return new int[]{leftBoundaryIndex, rightBoundaryIndex};
        }
        return new int[]{-1, -1};
    }

    /**
     * .寻找边界的统一二分：
     * .当 findLeft = true: 找第一个 >= target 的位置 (lower bound)
     * .当 findLeft = false: 找第一个 > target 的位置 (upper bound)
     * .若未找到满足条件的元素，返回 nums.length 作为“越界”标识。
     */
    private int findBoundary(int[] nums, int target, boolean findLeft) {
        int left = 0;
        int right = nums.length - 1;
        int ans = nums.length; // 默认越界（表示没找到合适位置）
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防止溢出的写法
            // 根据 findLeft 区分判断条件
            if (nums[mid] > target || (findLeft && nums[mid] >= target)) {
                // 当前 mid 满足条件（或大于 target），向左侧继续找更靠左的满足条件位置
                ans = mid; // 记录可能的答案
                right = mid - 1; // 缩小到左半部分
            } else {
                // nums[mid] < target 或 (findLeft=false 且 nums[mid]==target) 时向右找
                left = mid + 1; // 右移
            }
        }
        return ans;
    }

    // ===================== 测试代码区域 =====================
    public static void main(String[] args) {
        S63_Mid_34_在排序数组中查找元素的第一个和最后一个位置 solution = new S63_Mid_34_在排序数组中查找元素的第一个和最后一个位置();
        System.out.println("=== 在排序数组中查找元素的第一个和最后一个位置 测试开始 ===\n");

        // 1. 示例1
        testCase(solution, new int[]{5,7,7,8,8,10}, 8, new int[]{3,4}, "示例1: 正常中间重复");
        // 2. 示例2 (不存在)
        testCase(solution, new int[]{5,7,7,8,8,10}, 6, new int[]{-1,-1}, "示例2: 不存在目标");
        // 3. 空数组
        testCase(solution, new int[]{}, 0, new int[]{-1,-1}, "空数组");
        // 4. 单元素存在
        testCase(solution, new int[]{1}, 1, new int[]{0,0}, "单元素存在");
        // 5. 单元素不存在
        testCase(solution, new int[]{1}, 2, new int[]{-1,-1}, "单元素不存在");
        // 6. 全部相同且为目标
        testCase(solution, new int[]{2,2,2,2,2}, 2, new int[]{0,4}, "全部相同即为目标");
        // 7. 全部相同但不为目标
        testCase(solution, new int[]{3,3,3,3}, 2, new int[]{-1,-1}, "全部相同但不是目标");
        // 8. 目标在开头
        testCase(solution, new int[]{4,4,5,6,7}, 4, new int[]{0,1}, "目标在开头连续");
        // 9. 目标在末尾
        testCase(solution, new int[]{1,2,3,9,9,9}, 9, new int[]{3,5}, "目标在末尾连续");
        // 10. 目标仅出现一次中间位置
        testCase(solution, new int[]{1,2,3,4,5,6,7}, 4, new int[]{3,3}, "目标仅出现一次中间");
        // 11. 目标比所有元素都小
        testCase(solution, new int[]{5,6,7}, 1, new int[]{-1,-1}, "目标比所有元素小");
        // 12. 目标比所有元素都大
        testCase(solution, new int[]{5,6,7}, 10, new int[]{-1,-1}, "目标比所有元素大");
        // 13. 混合分布多个段
        testCase(solution, new int[]{1,2,2,2,3,4,4,4,5,5,5,6}, 5, new int[]{8,10}, "目标出现一段中间段");
        // 14. 两端都有接近值 (测试边界正确)
        testCase(solution, new int[]{2,2,3,4,4,4,5,6,6,7}, 4, new int[]{3,5}, "中间区间验证");
        // 15. 大数组性能简单验证
        int[] large = new int[1000];
        for (int i = 0; i < large.length; i++) {
            large[i] = i / 10; // 每个数字重复10次 0..99
        }
        testCase(solution, large, 57, new int[]{570,579}, "大数组性能与区间定位(57)");
        testCase(solution, large, 0, new int[]{0,9}, "大数组目标首段(0)");
        testCase(solution, large, 99, new int[]{990,999}, "大数组目标末段(99)");
        testCase(solution, large, 100, new int[]{-1,-1}, "大数组不存在目标(100)");

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .统一测试输出方法。
     */
    private static void testCase(S63_Mid_34_在排序数组中查找元素的第一个和最后一个位置 solution,
                                 int[] nums,
                                 int target,
                                 int[] expected,
                                 String description) {
        int[] actual = solution.searchRange(nums, target);
        boolean pass = actual[0] == expected[0] && actual[1] == expected[1];
        System.out.printf("%-20s | target=%d | 结果=[%d,%d] | 期望=[%d,%d] | %s\n",
                description, target, actual[0], actual[1], expected[0], expected[1], pass ? "✓" : "✗");
        assert pass : description + " 测试未通过";
    }
}
